/**
 * 给定二维数组，求最长递增路径。
 * 注意到起点在哪是未必的，但使用记忆化搜索的DP即可。
 * 实际搜索过程不会超出O(NM)的范围
 */
using llt = long long;
llt const MOD = 1E9 + 7;
int const None = 0x7F2F3F4F;

class Solution {

using vi = vector<int>;

int N, M;
vector<vi> D;

public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        static int const DR[] = {-1, 1, 0, 0};
        static int const DC[] = {0, 0, -1, 1};

        N = matrix.size();
        M = matrix[0].size();
        D.assign(N, vi(M, None));

        function<int(int, int)> __dfs = [&](int x, int y)->int{
            if(None != D[x][y]) return D[x][y];
            
            int ans = 1;
            for(int nr,nc,i=0;i<4;++i){
                nr = x + DR[i];
                nc = y + DC[i];
                if(0 <= nr and nr < N and 0 <= nc and nc < M and matrix[x][y] < matrix[nr][nc]){
                    ans = max(ans, 1 + __dfs(nr, nc));
                }
            }
            return D[x][y] = ans;
        };

        int ans = 0;
        for(int i=0;i<N;++i)for(int j=0;j<M;++j){
            ans = max(ans, __dfs(i, j));
        }
        return ans;
    }
};